/**
 * 22. 括号生成
 * https://leetcode-cn.com/problems/generate-parentheses/
 */
const { displayBaseArray } = require('../../libs/public');

const memory = new Map();
memory.set(0, []);
memory.set(1, ['()']);

/**
 * @param {number} n
 * @return {string[]}
 */
function generateParenthesis(n) {
  if (memory.has(n)) {
    return memory.get(n);
  }
  const set = new Set();
  for (let i = 0; i < n; i += 1) {
    const inner = generateParenthesis(i);
    const outer = generateParenthesis(n - i - 1);
    if (inner.length && outer.length) {
      for (let j = 0; j < inner.length; j += 1) {
        const left = `(${inner[j]})`;
        for (let k = 0; k < outer.length; k += 1) {
          set.add(`${left}${outer[k]}`);
        }
      }
    } else if (inner.length) {
      for (let j = 0; j < inner.length; j += 1) {
        set.add(`(${inner[j]})`);
      }
    } else {
      for (let k = 0; k < outer.length; k += 1) {
        set.add(`()${outer[k]}`);
      }
    }
  }
  const result = Array.from(set);
  memory.set(n, result);
  return result;
}

console.log(displayBaseArray(generateParenthesis(3)) === '[()()(),()(()),(())(),(()()),((()))]');
console.log(displayBaseArray(generateParenthesis(1)) === '[()]');
